package code.starivan.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Ivan on 2015/10/19.
 */

/*
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

        For example,
        If n = 4 and k = 2, a solution is:

        [
        [2,4],
        [3,4],
        [2,3],
        [1,2],
        [1,3],
        [1,4],
        ]
*/

public class N077_Combinations {
    public static void test(){
        List<List<Integer>> ret=new N077_Combinations().combine(4,2);
        for(int i=0;i<ret.size();i++){
            for(int j=0;j<ret.get(i).size();j++){
                System.out.print(ret.get(i).get(j)+" ");
            }

            System.out.print("\n");
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ret=new ArrayList<>();
        if(k<=0||k>n||n<=0){
            return ret;
        }

        int[] arr=new int[k];
        combine(0,k,1,n,ret,arr);

        return ret;
    }

    public void combine(int cur,int k,int start,int n,List<List<Integer>> ret,int[] arr){
        if(cur==k){
            ArrayList<Integer> a=new ArrayList<>();
            for(int i=0;i<arr.length;++i){
                a.add(arr[i]);
            }
            ret.add(a);
        }else{
            for(int i=start;i<=n;i++){
                arr[cur]=i;
                combine(cur+1,k,i+1,n,ret,arr);
            }
        }
    }
}
